//Given a string s containing just the characters '(', ')', '{', '}', '[' and ']
//', determine if the input string is valid. 
//
// An input string is valid if: 
//
// 
// Open brackets must be closed by the same type of brackets. 
// Open brackets must be closed in the correct order. 
// 
//
// 
// Example 1: 
//
// 
//Input: s = "()"
//Output: true
// 
//
// Example 2: 
//
// 
//Input: s = "()[]{}"
//Output: true
// 
//
// Example 3: 
//
// 
//Input: s = "(]"
//Output: false
// 
//
// Example 4: 
//
// 
//Input: s = "([)]"
//Output: false
// 
//
// Example 5: 
//
// 
//Input: s = "{[]}"
//Output: true
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length <= 104 
// s consists of parentheses only '()[]{}'. 
// 
// Related Topics 栈 字符串 
// 👍 2379 👎 0


package leetcode.editor.cn;

import java.util.Stack;

//Java：Valid Parentheses
class P20ValidParentheses {
    public static void main(String[] args) {
        Solution solution = new P20ValidParentheses().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<>();
            char[] chars = s.toCharArray();
            for (char ch : chars) {
                switch (ch) {
                    case '(':
                    case '[':
                    case '{':
                        stack.push(ch);
                        break;
                    case ')':
                        if (stack.size() == 0) {
                            return false;
                        }
                        if ('(' == (stack.peek())) {
                            stack.pop();
                        } else {
                            return false;
                        }
                        break;
                    case ']':
                        if (stack.size() == 0) {
                            return false;
                        }
                        if ('[' == (stack.peek())) {
                            stack.pop();
                        } else {
                            return false;
                        }
                        break;
                    case '}':
                        if (stack.size() == 0) {
                            return false;
                        }
                        if ('{' == stack.peek()) {
                            stack.pop();
                        } else {
                            return false;
                        }
                        break;

                }
            }
            return stack.size() == 0 ? true : false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}